using System.Collections.Generic;
using System;


namespace Super
{
	public class PriorityQueue<T> where T : IComparable
	{
		private List<T> dataList = new List<T>();
		private CountDictionary<T> coutDict = new CountDictionary<T>();
		private T lowerPriorityObj;

		public PriorityQueue()
		{
			dataList.Clear();
			coutDict.Clear();
		}

		public PriorityQueue(List<T> nodes)
		{
			dataList = new List<T>(nodes);
			coutDict = new CountDictionary<T>(nodes);

			int index = dataList.Count / 2 - 1;
			while (index >= 0)
			{
				Heapify(index);
				index--;
			}
		}

		public void ModifyPriorityHeapify(T value)
		{
			int index = 0;
			for (int i = 0; i < dataList.Count; i++)
			{
				if (dataList[i].Equals(value))
				{
					index = i;
					break;
				}
			}
			while (index >= 0)
			{
				Heapify(index);
				index--;
			}
		}

		public void Heapify(int index)
		{
			int priorityIndex = index;
			int leftIndex = index * 2 + 1;
			int rightIndex = index * 2 + 2;

			bool hasLeft = leftIndex < dataList.Count;
			if (hasLeft)
			{
				if (dataList[leftIndex].CompareTo(dataList[priorityIndex]) == -1)
					priorityIndex = leftIndex;
			}

			bool hasRight = rightIndex < dataList.Count;
			if (hasRight)
			{
				if (dataList[rightIndex].CompareTo(dataList[priorityIndex]) == -1)
					priorityIndex = rightIndex;
			}

			if (priorityIndex != index)
			{
				GlobalUtil.ListSwap(dataList, index, priorityIndex);
				Heapify(priorityIndex);
			}
		}

		public void Enqueue(T value)
		{
			dataList.Add(value);
			coutDict.Add(value);

			int index = dataList.Count - 1;
			int parentIndex = (index - 1) / 2;
			bool isPriority = dataList[index].CompareTo(dataList[parentIndex]) == -1;

			while (parentIndex >= 0 && isPriority)
			{
				GlobalUtil.ListSwap(dataList, index, parentIndex);

				index = parentIndex;
				parentIndex = (index - 1) / 2;
				isPriority = dataList[index].CompareTo(dataList[parentIndex]) == -1;
			}
		}

		public T Dequeue()
		{
			if (dataList.Count == 0)
				return default(T);

			GlobalUtil.ListSwap(dataList, 0, dataList.Count - 1);
			T result = dataList[dataList.Count - 1];
			dataList.RemoveAt(dataList.Count - 1);
			coutDict.Remove(result, 1);

			Heapify(0);
			return result;
		}

		public T Peek()
		{
			if (dataList.Count == 0)
				return default(T);

			return dataList[0];
		}

		public bool TryPeek(out T node)
		{
			if (dataList.Count == 0)
			{
				node = default(T);
				return false;
			}

			node = dataList[0];
			return true;
		}

		public void Delete(T value)
		{
			if (!coutDict.Contains(value))
				return;

			int index = 0;
			for (int i = 0; i < dataList.Count; i++)
			{
				if (dataList[i].Equals(value))
				{
					index = i;
					break;
				}
			}

			GlobalUtil.ListSwap(dataList, index, dataList.Count - 1);
			T result = dataList[dataList.Count - 1];
			dataList.RemoveAt(dataList.Count - 1);
			coutDict.Remove(result, 1);

			Heapify(index);
			return;
		}

		public int Count()
		{
			return dataList.Count;
		}

		public bool Contains(T value)
		{
			return coutDict.Contains(value);
		}

		#region 优先级最低

		public void UpdateLowerPriorityObj()
		{
			if (dataList.Count <= 0) return;
			lowerPriorityObj = dataList[0];

			for (int i = 0; i < dataList.Count; i++)
			{
				if (lowerPriorityObj.CompareTo(dataList[i]) == 1)
					lowerPriorityObj = dataList[i];
			}
		}
		
		#endregion
	}

}
